package by2019;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/*
 * 给定一个大小为n的数组，找到其中的众数。
 * 众数是指在数组中出现次数超过n/2的数
 */
public class 求众数 {

	public static void main(String[] args) {
		int[] nums = new int[] {11,22,33,22,11,22,22} ;
		int a = majorityElementX(nums);
		System.out.println(a);
	}
	//暴力法
	 public static int majorityElement(int[] nums) {
		 for(int i=0;i<nums.length;i++) {
			 int count = 0 ;
			 for(int j : nums) {
				 if(j==nums[i]) {
					 count ++ ;
				 }
			 }
			 if(count>nums.length/2)
				 return nums[i];
		 }
		 return -1 ;
	 }
	 
	 //利用map存值和count，最后在map中找count最大的数
	 public static int majorityElementX(int[] nums) {
		 Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		 int count = 1 ;
		 for(int i : nums) {
			 
			 if(!map.containsKey(i)) {
				 map.put(i, 1) ;
			 } else {
				count = map.get(i) ;
				count ++ ;
				map.put(i, count);
			 }
			 if(count>nums.length/2)
				return i ; 
		 }
		 return -1 ;
	 }
	 
	 //利用排序，因为众数的出现次数会超过n/2次
	 //所以只需要在排序后返回n/2处的值即可
	 public static int majorityElementPro(int[] nums) {
		 Arrays.sort(nums);
		 return nums[nums.length/2] ;
	 }
}
